import java.util.*;

 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

public class Test {
    // 题目 1： 杨辉三角
    // 卡在了不知道怎么解决第一行与第二行放入列表中！
    public List<List<Integer>> generate(int rows) {
        List<List<Integer>> lists = new LinkedList<>();
        for(int i = 0; i < rows; i++){
            List<Integer> list = new LinkedList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    list.add(1);
                }else{
                    List<Integer> temp = lists.get(i - 1);
                    list.add(temp.get(j) + temp.get(j - 1));
                }
            }
            lists.add(list);
        }
        return lists;
    }

    // 题目2：杨辉三角Ⅱ
    public List<Integer> getRow1(int rowIndex) {
        List<Integer> temp = null;
        for(int i = 0; i <= rowIndex; i++){
            List<Integer> list = new LinkedList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    list.add(1);
                }else{
                    list.add(temp.get(j) + temp.get(j - 1));
                }
            }
            temp = list;
        }
        return temp;
    }

    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new LinkedList<>();
        for(int i = 0; i <= rowIndex; i++){
            List<Integer> temp = new LinkedList<>();
            for(int j = 0; j <= i; j++){
                if(j == 0 || j == i){
                    temp.add(1);
                }else{
                    temp.add(list.get(j) + list.get(j - 1));
                }
            }
            list = temp;
        }
        return list;
    }

    // 题目 3：验证搜索二叉树
    // 再次写出解答，依旧很繁琐。
    // 可以直接调用 函数
    public boolean isValidBST1(TreeNode root) {
        long upper = Long.MAX_VALUE;
        long lower = Long.MIN_VALUE;

        boolean left =  isValidSubBST1(root.left, lower, root.val);
        boolean right = isValidSubBST1(root.right, root.val, upper);

        return left && right;
    }

    private boolean isValidSubBST1(TreeNode root, long lower, long upper){
        if(root == null){
            return true;
        }
        if(root.val <= lower || root.val >= upper){
            return false;
        }

        boolean left = isValidSubBST1(root.left, lower, root.val);
        boolean right = isValidSubBST1(root.right, root.val, upper);

        return left && right;
    }

    // 这样写更简略一些！
    public boolean isValidBST2(TreeNode root) {
        return isValidSubBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidSubBST(TreeNode root, long lower, long upper){
        if(root == null){
            return true;
        }

        if(root.val <= lower || root.val >= upper){
            return false;
        }

        return isValidSubBST(root.left, lower, root.val) && isValidSubBST(root.right, root.val, upper);
    }

    // 二叉搜索树的中序遍历是依次递增的，可使用队列。
    // 并没有一看到这个题目立马想到这个特征！
    Deque<TreeNode> queue = new LinkedList<>();
    public boolean isValidBST3(TreeNode root) {
        if(root == null){
            return true;
        }

        boolean left = isValidBST(root.left);
        if(!queue.isEmpty()){
            if(root.val <= queue.pollLast().val){
                return false;
            }
        }

        queue.offer(root);

        boolean right = isValidBST(root.right);

        return left && right;
    }

    // 上述可进一步简化，因为每次比较只是队列的最后一个元素，可以用一个 pre
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }

        if(!isValidBST(root.left)){
            return false;
        }

        if(root.val <= pre){
            return false;
        }

        pre = root.val;

        return isValidBST(root.right);
    }

}
